/**
 * @file   Heap.h
 * @author xingyifan
 * @date   2021/08/21 15:38:05
 * 
 * @brief  heap sort
 * 
 * 
 */

#include "Heap.h"

void Heap::shiftdown(int i)
{
    int l = LEFTCHILD(i);
    int r = RIGHTCHILD(i);
    int max = i;
    if (l < size && value[l] > value[max])
    {
        max = l;
    }
    if (r < size && value[r] > value[max])
    {
        max = r;
    }
    if (max != i)
    {
        double tmp = value[i];
        value[i] = value[max];
        value[max] = tmp;
        shiftdown(max);
    }
}

void Heap::build()
{
    for (int i = PARENT(size - 1); i >= 0; i--)
    {
        shiftdown(i);
    }
}

void Heap::sort()
{
    build();
    for (int i=const_size-1;i>0;i--) {
        double tmp = value[i];
        value[i] = value[0];
        value[0] = tmp;

        size--;
        shiftdown(0);
    }
    size = const_size;
}